#
# @lc app=leetcode.cn id=29 lang=python3
#
# [29] 两数相除
#


# @lc code=start
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        sign = -1 if (dividend < 0) ^ (divisor < 0) else 1
        dividend, divisor = abs(dividend), abs(divisor)

        count = 0
        while dividend >= (divisor << (count + 1)):
            count += 1

        result = 0
        while dividend >= divisor and count >= 0:
            while dividend < divisor << count:
                count -= 1

            result += 1 << count
            dividend -= divisor << count
            count -= 1

        result *= sign
        return result if -(1 << 31) <= result <= (1 << 31) - 1 else (1 << 31) - 1


# @lc code=end
